package P34_数组查找第一个和最后一个;

import java.util.Arrays;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例 2：
 * <p>
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 * <p>
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 */
public class Solution {
    int min = -1, max = -1;

    public void search(int[] nums, int target, int left, int right, boolean searchLeft) {
        if (left > right) {
            return;
        }
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            if (min == -1 && max == -1) {
                min = max = mid;
            }
            if (searchLeft) {
                min = mid;//Math.min(mid, min);
            } else {
                max = mid;//Math.max(max, mid);
            }
            //找最大的，但是前提是比当前max可找的范围大，要不然没用
            if (max < right) {
                search(nums, target, Math.max(max, mid + 1), right, false);
            }
            //往左找最小的，最小的index可能为left，但是如果min已经比left小了，就不用继续了
            if (min > left) {
                search(nums, target, left, Math.min(min, mid - 1), true);
            }
            return;
        }

        if ((searchLeft && min != -1 && min < mid + 1) || (!searchLeft && max > right)) {
            return;
        }
        if (nums[mid] < target) {
            search(nums, target, mid + 1, right, searchLeft);
        } else {
            search(nums, target, left, mid - 1, searchLeft);
        }
    }

    public int[] searchRange(int[] nums, int target) {
        search(nums, target, 0, nums.length - 1, true);
        return new int[]{min, max};

    }

    public static void main(String args[]) {
        System.out.println(Arrays.toString(new P34_数组查找第一个和最后一个.Solution().searchRange(new int[]{-8, 2, 3, 4, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 11, 11}, 8)));
    }
}
